package 面试2025.高德地图;

import java.util.Arrays;

public class Test {
    //{1,2,3,5,6,7,8,7,2,3,2,8};

    /**
     * 算法题：给出一个数组，返回最长连续递增数组[5,6,7,8]
     * 当时没处理好左边界
     * 思想来源于：最长连续递增序列_674
     */
    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,5,6,7,8,7,2,3,2,8};
        int[] judge = judge(arr);
        System.out.println(Arrays.toString(judge));
    }

    /**
     * 动态规划
     */
    public static int[] judge(int[] arr){
        int[] dp = new int[arr.length];
        for(int i = 0;i < arr.length;i++) dp[i] = 1;
        int res = 1;
        int left = 0, right = 0;
        for(int i = 1;i < arr.length;i++){
            if(arr[i] - arr[i - 1] == 1){
                dp[i] = dp[i - 1] + 1;
            }
            if(dp[i] > res) {
                res = dp[i];
                right = i;
                left = i - res + 1;
            }
        }
        int[] nums = new int[right - left + 1];
        int k = 0;
        for(int i = left;i <= right;i++){
            nums[k] = arr[i];
            k++;
        }
        System.out.println(Arrays.toString(nums));
        return nums;
    }

    /**
     * 双指针
     */
    public static int[] judge2(int[] arr){
        int left = 0, right = 0, cur = 0;
        int res = 0;
        int start = 0, end = 0;
        for(int i = 1;i < arr.length;i++){
            if(arr[i] - arr[i - 1] == 1){
                left = i - 1;
            }else{
                continue;
            }
            while(arr[i] - arr[i - 1] == 1){
                i++;
            }
            right = i - 1;
            if(right - left + 1 > res){
                res = right - left + 1;
                start = left;
                end = right;
            }
        }
        int[] nums = new int[end - start + 1];
        int k = 0;
        for(int i = start;i <= end;i++){
            nums[k] = arr[i];
            k++;
        }
        return nums;
    }

    /**
     * 有细节问题
     */
    public static ListNode Sort(ListNode head){
        ListNode dummy = new ListNode(101);
        dummy.next = head;
        ListNode mid = getMid(head);
        mid.next = null;
        ListNode l1 = Sort(head);
        ListNode l2 = Sort(mid);
        mergeSort(l1, l2);
        return dummy.next;
    }
    private static void mergeSort(ListNode list1, ListNode list2){
        ListNode temp = new ListNode(101);
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                temp.next = list1;
                list1 = list1.next;
            }else{
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1 == null ? list2 : list1;
    }
    private static ListNode getMid(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
